package codetop.microsoft.T1095;

/**
 * @Author: 18362
 * @Create: 2022-09-11 14:36:15 星期日
 */
class Solution {
    /**
     * 思路：多次二分查找即可，先二分找到山脉顶点，然后优先在左边的升序数组中寻找，再在右边的降序数组中寻找
     */
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.length();
        int mid = findMid(mountainArr, n);
        if (target == mountainArr.get(mid))
            return mid;
        int left = findLeft(mountainArr, 0, mid - 1, target);
        if (left >= 0)
            return left;
        return findRight(mountainArr, mid + 1, n - 1, target);
    }

    private int findMid(MountainArray mountainArr, int n) {
        int left = 1, right = n-1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int a = mountainArr.get(mid-1), b = mountainArr.get(mid), c = mountainArr.get(mid+1);
            if (b > a && b > c)
                return mid;
            else if (a > b && b > c)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left;
    }

    private int findLeft(MountainArray mountainArr, int left, int right, int target) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            int b = mountainArr.get(mid);
            if (b == target)
                return mid;
            else if (b > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return mountainArr.get(left) == target ? left : -1;
    }

    private int findRight(MountainArray mountainArr, int left, int right, int target) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            int b = mountainArr.get(mid);
            if (b == target)
                return mid;
            else if (b > target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return mountainArr.get(left) == target ? left : -1;
    }
}
